﻿//class Solution
//{
//public:
//	bool lemonadeChange(vector<int>& bills)
//	{
//		int five = 0, ten = 0;
//		for (auto x : bills)
//		{
//			if (x == 5) five++; 
//			else if (x == 10) // 10 元：找零 5 元
//			{
//				if (five == 0) return false;
//				five--; ten++;
//			}
//			else // 20 元
//			{
//				if (ten && five) 
//				{
//					ten--; five--;
//				}
//				else if (five >= 3)
//				{
//					five -= 3;
//				}
//				else return false;
//			}
//		}
//		return true;
//	}
//};

//class Solution
//{
//public:
//	int halveArray(vector<int>& nums)
//	{
//		priority_queue<double> heap; // 创建⼀个⼤根堆
//		double sum = 0.0;
//		for (int x : nums) // 把元素都丢进堆中，并求出累加和
//		{
//			heap.push(x);
//			sum += x;
//		}
//		sum /= 2.0; // 先算出⽬标和
//		int count = 0;
//		while (sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下
//		{
//			double t = heap.top() / 2.0;
//			heap.pop();
//			sum -= t;
//			count++;
//				heap.push(t);
//		}
//		return count;
//	}
//};



//class Solution
//{
//public:
//	string largestNumber(vector<int>& nums)
//	{
//		//把所有的数转化成字符串
//		vector<string> strs;
//		for (int x : nums) strs.push_back(to_string(x));
//		// 排序
//		sort(strs.begin(), strs.end(), [](const string& s1, const string& s2)
//			{
//				return s1 + s2 > s2 + s1;
//			});
//		// 提取结果
//		string ret;
//		for (auto& s : strs)
//			ret += s;
//		if (ret[0] == '0') 
//			 return "0";
//		return ret;
//	}
//};


class Solution
{
public:
	int wiggleMaxLength(vector<int>& nums)
	{
		int n = nums.size();
		if (n < 2) return n;
		int ret = 0, left = 0;
		for (int i = 0; i < n - 1; i++)
		{
			int right = nums[i + 1] - nums[i]; // 计算接下来的趋势
			if (right == 0) 
				continue; // 如果⽔平，直接跳过
			if (right * left <= 0) 
				ret++; // 累加波峰或者波⾕
			left = right;
		}
		return ret + 1;
	}
};